package com.shm.leetcode;

/**
 * 859. 亲密字符串
 * 给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。
 *
 * 交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。
 *
 * 例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。
 *
 *
 * 示例 1：
 *
 * 输入：s = "ab", goal = "ba"
 * 输出：true
 * 解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。
 * 示例 2：
 *
 * 输入：s = "ab", goal = "ab"
 * 输出：false
 * 解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。
 * 示例 3：
 *
 * 输入：s = "aa", goal = "aa"
 * 输出：true
 * 解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。
 * 示例 4：
 *
 * 输入：s = "aaaaaaabc", goal = "aaaaaaacb"
 * 输出：true
 *
 *
 * 提示：
 *
 * 1 <= s.length, goal.length <= 2 * 104
 * s 和 goal 由小写英文字母组成
 * @author SHM
 */
public class BuddyStrings {
    /**
     * 方法一：枚举
     * 思路与算法
     *
     * 设两个字符串分别为 ss 和 \textit{goal}goal，其中 s[i]s[i] 表示 ss 的第 ii 个字符，其中 \textit{goal}[i]goal[i] 表示 \textit{goal}goal 的第 ii 个字符。如果 s[i] = \textit{goal}[i]s[i]=goal[i]，我们就说 ii 是匹配的，否则称 ii 是不匹配的。亲密字符串定义为：需要交换 ss 中的第 ii 个字符 s[i]s[i] 与 \textit{s}s 中第 jj 个字符且满足 i \neq ji
     * 
     * ​
     *  =j，交换后 ss 与 \textit{goal}goal 相等。亲密字符串的两个字符串需要交换一次索引不相等的两个字符后相等。
     *
     * 如果满足交换 s[i]s[i] 和 s[j]s[j] 后两个字符串相等，那么需要满足以下几个条件使得 ss 和 \textit{goal}goal 为亲密字符串：
     *
     * 字符串 ss 的长度与字符串 \textit{goal}goal 的长度相等；
     * 存在 i \neq ji
     * 
     * ​
     *  =j 且满足 s[i] = \textit{goal}[j]s[i]=goal[j] 以及 s[j] = \textit{goal}[i]s[j]=goal[i]，实际在 s[i], s[j], \textit{goal}[i], \textit{goal}[j]s[i],s[j],goal[i],goal[j] 这四个自由变量中，只存在两种情况：
     * 满足 s[i] = s[j]s[i]=s[j]：则此时必然满足 s[i] = s[j] = \textit{goal}[i] = \textit{goal}[j]s[i]=s[j]=goal[i]=goal[j]，字符串 ss 与 \textit{goal}goal 相等，我们应当能够在 ss 中找到两个不同的索引 i,ji,j，且满足 s[i] = s[j]s[i]=s[j]，如果能够找到两个索引不同但值相等的字符则满足 ss 与 \textit{goal}goal 为亲密字符串；否则不为亲密字符串。
     * 满足 s[i] \neq s[j]s[i]
     * 
     * ​
     *  =s[j]：满足 s[i] = \textit{goal}[j], s[j] = \textit{goal}[i], s[i] \neq s[j]s[i]=goal[j],s[j]=goal[i],s[i]
     * 
     * ​
     *  =s[j] 的情况下，两个字符串 ss 与 \textit{goal}goal 除了索引 i,ji,j 以外的字符都是匹配的。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N)O(N)，其中 NN 为字符串的长度。我们至多遍历字符串两遍。
     *
     * 空间复杂度：O(C)O(C)。需要常数个空间保存字符串的字符统计次数，我们统计所有小写字母的个数，因此 C = 26C=26。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/buddy-strings/solution/qin-mi-zi-fu-chuan-by-leetcode-solution-yyis/
     * @param s
     * @param goal
     * @return
     */
    public boolean buddyStrings(String s, String goal) {
        if(s.length()!=goal.length()){
            return false;
        }
        int left=0,right = s.length()-1;
        int cnt = 0;
        if (s.equals(goal)){
            int[] count = new int[26];
            for (int i = 0; i < s.length(); i++) {
                int j = s.charAt(i) - 'a';
                count[j]++;
                if (count[j] >1){
                    return true;
                }
            }
            return false;
        }else {
//            while (left < right) {
//                while (left < s.length() - 1 && s.charAt(left) == goal.charAt(left)) {
//                    left++;
//                }
//                while (right > 0 && s.charAt(right) == goal.charAt(right)) {
//                    right--;
//                }
//                if (s.charAt(left) == goal.charAt(right) && s.charAt(right) == goal.charAt(left)) {
//                    cnt++;
//                }
//                left++;
//                right--;
//            }
//            return cnt == 1;

            int first = -1,second = -1;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i)!=goal.charAt(i)){
                    if (first==-1){
                        first=i;
                    }else if (second==-1){
                        second=i;
                    }else {
                        return false;
                    }
                }
            }
            return second!=-1&&s.charAt(first)==goal.charAt(second)&&s.charAt(second)==goal.charAt(first);
        }
    }

    /**
     * 模拟
     * 根据题意进行模拟即可，搞清楚什么情况下两者为「亲密字符」：
     *
     * 当 ss 与 goalgoal 长度 或 词频不同，必然不为亲密字符；
     * 当「ss 与 goalgoal 不同的字符数量为 22（能够相互交换）」或「ss 与 goalgoal 不同的字符数量为 00，但同时 ss 中有出现数量超过 22 的字符（能够相互交换）」时，两者必然为亲密字符。
     *
     * 时间复杂度：令 nn 为两字符串之间的最大长度，CC 为字符集大小，CC 固定为 2626，复杂度为 O(n + C)O(n+C)
     * 空间复杂度：O(C)O(C)
     *
     * 作者：AC_OIer
     * 链接：https://leetcode-cn.com/problems/buddy-strings/solution/gong-shui-san-xie-jian-dan-zi-fu-chuan-m-q056/
     * @param s
     * @param goal
     * @return
     */
    public boolean buddyStrings_1(String s, String goal) {
        int n = s.length(),m= goal.length();
        if (n != m) {
            return false;
        }
        int[] cntS = new int[26],cntG = new int[26];
        int sum =0;
        for (int i = 0; i < n; i++) {
            int a=s.charAt(i)-'a',b=goal.charAt(i)-'a';
            cntS[a]++;
            cntG[b]++;
            if (a!=b){
                sum++;
            }
        }
        boolean ok = false;
        for (int i = 0; i < 26; i++) {
            if (cntS[i]!=cntG[i]){
                return false;
            }
            if (cntS[i]>1){
                ok = true;
            }
        }
        return sum==2||(sum==0&&ok);
    }
}
